//给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
//
//
// 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
//
//
// 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
//
// 以这种方式修改数组后，返回数组 可能的最大和 。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,2,3], k = 1
//输出：5
//解释：选择下标 1 ，nums 变为 [4,-2,3] 。
//
//
// 示例 2：
//
//
//输入：nums = [3,-1,0,2], k = 3
//输出：6
//解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
//
//
// 示例 3：
//
//
//输入：nums = [2,-3,-1,5,-4], k = 2
//输出：13
//解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -100 <= nums[i] <= 100
// 1 <= k <= 10⁴
//
//
// Related Topics 贪心 数组与矩阵 排序 👍 356 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function largestSumAfterKNegations(nums: number[], k: number): number {

    nums.sort((a, b) => Math.abs(b) - Math.abs(a));
    let curIndex: number = 0;
    const length = nums.length;
    while (curIndex < length && k > 0) {
        if (nums[curIndex] < 0) {
            nums[curIndex] *= -1;
            k--;
        }
        curIndex++;
    }
    //? 即所有的负数都变正了
    while (k > 0) {
        nums[length - 1] *= -1;
        k--;
    }
    return nums.reduce((pre, cur) => pre + cur, 0);
};
//leetcode submit region end(Prohibit modification and deletion)

function largestSumAfterKNegations2(nums: number[], k: number): number {


    /*
    ? 首先先把负数按顺序换一边。如果K次还没到，则此时有两个情况
        ? 1. k是奇数 则一定会有一个数变反 需要对最小的那个数操作
        ? 2. k是偶数 则换谁都可以
     */
    let minNum :number
    let leftK : number = 0
    let result : number = 0
    //? 必须要写回调函数不然负数排序会出问题，绝对值小的会排前面
    nums.sort((a,b)=>{
        return a - b
    })
    for (let i = 0; i < nums.length; i ++) {
        if (nums[i] < 0 && k) {
            nums[i] = -nums[i]
            //? 负数挨着换
            k --
        }
        else if (nums[i] === 0) {
            //? 全部处理掉
            k = 0
        }
        else if (nums[i] > 0 && k){
            if (i === 0) {
                if (k % 2 === 1) {
                    nums[i] = -nums[i]
                }
            }
            else {
                if (nums[i] > nums[i - 1]) {
                    if (k % 2 === 1) {
                        result -= nums[i - 1] * 2
                        nums[i - 1] = -nums[i - 1]

                    }
                }
                else {
                    if (k % 2 === 1) {
                        nums[i] = -nums[i]
                    }
                }
            }
            //? 全部处理掉
            k = 0
        }
        result += nums[i]
        // console.log(nums);
    }
    //? 针对k大于数组长度的情况
    if (k % 2 === 1) {
        result -= 2 * nums.sort()[0]
    }
    return result
};
